Mine Sweeper (Due January 3^rd)

Mine sweeper is a puzzle played on a rectangular board divided into equal sized squares. Some of these squares have mines under them. The game starts with all squares closed and the aim of the player is to open all the squares except the ones that have mines. If a 'mine-square' is opened, the player loses the game. In each of the open squares which do not contain a mine, a number is written, which represents how many of its eight neighbors have mines in them.

Our aim is not to solve a Mine Sweeper puzzle, but to help in generating one. You are given a board with some squares open that do not contain mines and have the numbers of neighboring mines written as necessary. Your task is to lay a given number of mines in closed squares such that numbers in all open squares are fulfilled, i.e., there should not be an open square which has a different number of neighboring mines than the number written in it. There won't be mines on the board other than the ones you put.

Assumptions

The board will be of size N x M where 2 £ N £ 20 and 2 £ M £ 20.
The number of mines that you are asked to put is K where 1 £ K £ 20.
Of all the squares in the board given to you, at least 20% and at most 80% will be opened.
You will be able to lay all K mines on the given board in at least one configuration. If there are more than one different possible configurations, you should give only one of them as the solution.
The smallest row and column coordinate is zero.
Input data is error-free, no need to check for correctness.

Input

The input file is named mine.inp. The first line of this file contains three integers, N, M and K respectively, representing board dimensions and number of mines. In each the following N lines, there are M integers. The j^th integer on the (i + 1)^st line corresponds to the j^th column and i^th row of the board which is represented with the coordinates (i-1, j-1). If this integer is -1, then the corresponding square is closed; if this integer is a non-negative integer l, then the square is an opened one with the number l written in it.

Output

The output file is named mine.out. There should be only integers in the output file and the file should consist of K lines. Each of these K lines should have coordinates of a single mine in row, column order.

Example

mine.inp

4 6 6

-1 -1 -1 -1 2 -1

-1 -1 2 2 -1 -1

3 -1 -1 -1 -1 -1

-1 -1 2 -1 -1 0

mine.out

1 4

3 1

2 1

0 0

1 0

0 3

Hint: You can use an exhaustive search but you are expected to improve your algorithm with heuristics. There will be a bonus for the solution that solves the problem in shortest time! So try to find good heuristics to reduce the running time.

Regulations

Your source file should be named mine.c or mine.cpp. Your program should take no more than 15 seconds to run on Ineks 1-36. You will submit your homework as a single tar file using "submit315" command. Tar file must contain the following files

1. Makefile
2. mine.c[pp]
3. Other source code or user defined include files if any.

You can modify the sample Makefile given below to suit your needs. Use the command "make" to compile your program.

--- Makefile ---
all: mine
mine: mine.c
[TAB]g++ -Wall -O3 -o mine mine.c
--- End of Makefile ---

Please replace [TAB] with tab character.

CENG 315 Algorithms

HW # 5